package sort.select;

import java.util.Arrays;

public class HeapSort {
	//逻辑结构，堆树
	//物理结构，数组

	public int[] heapSort1(int[] array) {
		int temp = 0;
		for (int i = array.length-1; i > 0; i--) {
			for (int j = 0;j <= i;j++) {
				insertHeap(array, j);
			}
			temp = array[0];
			array[0] = array[i];
			array[i] = temp;
		}
		return array;
	}

	public int[] heapSort2(int[] array) {
		int temp = 0;
		setHeap(array);
		for (int i = array.length-1; i >= 0; i--) {
			temp = array[0];
			array[0] = array[i];
			array[i] = temp;

			sinkHeap(array, 0, i);
		}
		return array;
	}


	//最大堆，将index位置的数值向上上浮数组合适位置
	public static void insertHeap(int[] array,int index) {
		//记录index下标的数值，子节点的值
		int temp = array[index];
		//引索父节点
		int i = (index-1)/2;
		//循环条件，判断父子节点到达最大堆顶端后
		while(i >= 0 && index > 0) {
			//判断，父节点大于子节点
			if(array[i] >= temp)
			{
				break;
			} else {
				array[index] = array[i];
				index = i;
				i = (index-1)/2;
			}
			//子节点值移动位置
			array[index] = temp;
		}
	}

	//最大堆，将index位置的数值向下下沉到合适位置，循环写法
	public static void sinkHeap(int[] array,int index,int length) {
		//引索左叶子节点位置
		int i = index*2+1;
		//记录index下标的数值，父节点的值
		int temp = array[index];
		//判断，存在左孩子
		while(i < length) {
			//判断右孩子,选择左右孩子中最大的
			if(i+1 < length && array[i+1] > array[i]) {
				i++;
			}
			//判断，孩子节点值小于父节点，退出
			if(array[i] <= temp) {
				break;
			}
			//父节点的值更新
			array[index] = array[i];
			//父节点位置下移
			index = i;
			//新增左孩子节点位置
			i = index*2+1;
		}
		//赋值，父节点新位置值更改
		array[index] = temp;
	}

	//最大堆，将index位置的数值向下下沉到合适位置,递归写法
	public static void submergeHeap(int[] array,int index,int length) {
		if(index < length) {
			//设最大值下标
			int max = index;
			//左右孩子下标位置
			int left = index*2+1;
			int right = index*2+2;

			//三节点，索引最大值下标
			if(left < length) {
				if(array[max] < array[left]) {
					max = left;
				}
			}
			if(right < length) {
				if(array[max] < array[right]) {
					max = right;
				}
			}

			//判断，交换父子节点值，父节点下标下移
			if(max != index) {
				int temp = array[index];
				array[index] = array[max];
				array[max] = temp;

				//下沉至合适位置
				submergeHeap(array, max, length);
			}
		}
	}

	//最大堆初始化
	public void setHeap(int[] array) {
		//从后往前，第一个父节点开始
		for (int i = (array.length-1)/2; i >= 0; i--) {
			sinkHeap(array, i, array.length);
		}
	}

	public static void main(String[] args) {
		int array[];
		HeapSort test = new HeapSort();
		int[] array1 = {4,5,8,2,3,9,7,1};
		int[] array2 = {4,5,67,8,23423,45,43,67,23,2,5,4};
		int[] array3 = {4,5,8,2,3,9,7,1};
		System.out.println(Arrays.toString(array1));
		array = test.heapSort1(array1);
		System.out.println(Arrays.toString(array));

		System.out.println("\nheapSort2:");
		System.out.println(Arrays.toString(array3));
		array = test.heapSort2(array3);
		System.out.println(Arrays.toString(array));

	}

}
